# coding: utf-8
# 《算法图解》
# 二分查找实现
# 二分查找要求序列是有序的，有序的序列用二分查找也是最好的，性能是logN（虽然哈希很快，但是有空间成本N）
# 二分查找算法细节详解: https://www.cnblogs.com/mxj961116/p/11945444.html
# 二分查找是一种玄学算法，使用函数编程写特别麻烦，里面有些细节比较容易忽略！
# 关键词：low，high，mid，guess。

def binary_search(list, item):
    low=0
    #这里取最后一个元素，而不是length
    high=len(list)-1
    #使用<，会导致找不到最后一个元素，因此使用<=
    while low<=high:
        #奇数个得到中间，偶数个得到中间偏左
        mid=(low+high)/2
        guess=list[mid]
        if item==guess:
            return {"pos":mid, "val":item}
        elif item<guess:
            high=mid-1
        else:
            low=mid+1
    return None

#递归写法
def binary_search2(lst,item,low,high):
    # 递归的写法需要处理空数组的情况
    if len(lst)<=0:
        return None
    if low<=high:
        mid=(low+high)/2
        guess=lst[mid]
        if item==guess:
            return {"pos":mid, "val":guess}
        elif item<guess:
            return binary_search2(lst,item,low,mid-1)
        else:
            return binary_search2(lst,item,mid+1,high)
    return None

seq=[1,2,3,4,5,6,7,8,9,10]
seq2=[]
seq3=[1]
print(binary_search(seq,10))
print(binary_search(seq2,1))
print(binary_search(seq3,1))
print(binary_search2(seq,10,0,len(seq)))
print(binary_search2(seq2,1,0,len(seq2)))
print(binary_search2(seq3,1,0,len(seq3)))
